package heap.heapify;

import sortingAdvance.quickSort2Ways.InsertionSort;
import sortingAdvance.quickSort2Ways.SortTestHelper;

/**
 * 双路快速排序，解决大量重复元素，两边树不平衡的问题
 * mxf
 * 2018年5月28日14:08:42
 */
public class QuickSort2Ways {

    public static void sort(Comparable[] arr) {
        int length = arr.length;
        sort(arr, 0, length - 1);
    }

    private static void sort(Comparable[] arr, int l, int r) {
        if(r - l <= 15) {
            InsertionSort.sort(arr, l, r);
            return;
        }
        int p = partition(arr, l, r);
        sort(arr, l, p - 1);
        sort(arr, p + 1, r);
    }

    private static int partition(Comparable[] arr, int l, int r) {
        // 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot
        swap( arr, l , (int)(Math.random()*(r-l+1))+l );

        int i = l + 1;
        int j = r;
        Comparable v = arr[l];
        // arr[l+1...i) <= v; arr(j...r] >= v
        while (true) {
            while (i <= r && arr[i].compareTo(v) < 0)
               i++;
            while (j > l + 1 && arr[j].compareTo(v) > 0)
                j--;
            if(i > j) {
                break;
            }
            // 将等于v的元素平均分配到两端
            swap(arr, i, j);
            i++;
            j--;
        }
        swap(arr, l, j);
        return j;
    }

    private static void swap(Comparable[] arr, int l, int r) {
        Comparable v = arr[l];
        arr[l] = arr[r];
        arr[r] = v;
    }

    public static void main(String[] args) {
        Integer[] arr = SortTestHelper.generateRandomArray(1000000, 0, 10);
        QuickSort2Ways.sort(arr);
        SortTestHelper.printArray(arr);
    }
}
